package 数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/merge-intervals/
 */
public class _56_合并区间 {
    /**
     * 排序
     * @param intervals 目标二维数组
     * @return int[][]
     */
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return intervals;
        }
        // 对数组进行排序  通过第一个下标值排序
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        // 定义一个存储内存
        List<int[]> ans = new ArrayList<>();
        int n = intervals.length;
        // 声明一个中间比较值
        int[] temp = intervals[0];
        for (int i = 1; i < n; ++i) {
            /*
                进行比较 如果比较值的右区间 大于或等于 当前目标值的左区间 则需要合并
                否则将temp存入List

             */
            if (temp[1] >= intervals[i][0]) {
                temp[1] = Math.max(temp[1], intervals[i][1]);
            } else {
                ans.add(temp);
                temp = intervals[i];
            }
        }
        ans.add(temp);
        // 将List 转换成为 数组
        return ans.toArray(new int[ans.size()][2]);
    }
}
